#include<stdio.h>
int fen(int n,int m)
{
	if(m==1 || n==0)
		return 1;
	if(m>n)
		return fen(n,n);
	else
		return fen(n,m-1)+fen(n-m,m);
}
int main()
{
	int i;
	int n,m;
	scanf("%d",&i);
	//printf("%d\n",i);
	while(i--)
	{
		scanf("%d",&n);
		scanf("%d",&m);
		//printf("%lld %lld\n",n,m);
		printf("%d\n",fen(n,m));
	}
	return 0;
}
